#include <iostream>
#include <vector>

#include "TestCaseGenerator.h"

using namespace std;

void Swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

void ReorderArray(vector<vector<int>> &bucket, vector<int> &array)
{
	int index = 0;
	for (int i = 0; i < bucket.size(); i++)
	{
		for (int j = 0; j < bucket[i].size(); j++)
		{
			array[index++] = bucket[i][j];
		}
		bucket[i].clear();
	}
}
	
void RadixSort(vector<int> &array)
{
	int length = array.size();
	if (length <= 1)
		return;

	int maxNum = array[0];
	for (int i = 0; i < length; i++)
	{
		if (maxNum < array[i])
			maxNum = array[i];
	}

	int digitNum = 0;
	while (maxNum)
	{
		maxNum /= 10;
		digitNum++;
	}

	vector<vector<int>> bucket;
	bucket.resize(10);
	int currentDigit = 0;
	while (currentDigit <= digitNum)
	{
		for (int i = 0; i < length; i++)
		{
			int idx = (array[i] / static_cast<int>(std::pow(10, currentDigit))) % 10;
			bucket[idx].push_back(array[i]);
		}
		ReorderArray(bucket, array);

		currentDigit++;
	}
	
}

int main()
{
	shared_ptr<TestCaseGenerator> tcgPtr;

	vector<int> testCaseArray = tcgPtr->GenerateTestCase(20, 0, 1000);
	cout << " Before sort: testCaseArray: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;
	RadixSort(testCaseArray);
	cout << " After sort: testCaseArray: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;

	vector<int> testCaseArray1 = tcgPtr->GenerateTestCase();
	cout << " Before sort: testCaseArray1: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;
	RadixSort(testCaseArray1);
	cout << " After sort: testCaseArray1: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;
	

	return 0;
}